package acwing.lq.递归and递推;

import java.util.Scanner;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/11/10
 */
public class 递归实现排列型枚举 {

    static int N = 9;
    static int[] way = new int[N];
    static boolean[] flag = new boolean[N]; // 标记数字的状态
    static int n;


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        dfs(0);
    }

    private static void dfs(int u) {

        if (u == n) {
            for (int i = 0; i < n; i++) {
                System.out.print(way[i] + " ");
            }
            System.out.println();
            return;
        }
       for (int i = 0; i < n; i++) {
           if (!flag[i]) {
               flag[i] = true;
               way[u] = i + 1;
               dfs(u + 1);
               flag[i] = false;
           }
       }
    }
}
